package tree;

import org.checkerframework.checker.units.qual.C;

public class BinaryTreeMaximumPathSum124 {

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Context context = new Context(0, Integer.MIN_VALUE);
        maxPathSumRecursively(root, context);
        return context.pathMaxSum;
    }

    // 保证root一定非null, 才好比较context.pathMaxSum
    public void maxPathSumRecursively(TreeNode root, Context context) {
        int leftDepthMaxSum = Integer.MIN_VALUE;
        if (root.left != null) {
            maxPathSumRecursively(root.left, context);
            leftDepthMaxSum = context.depthMaxSum;
        }

        int rightDepthMaxSum = Integer.MIN_VALUE;
        if (root.right != null) {
            maxPathSumRecursively(root.right, context);
            rightDepthMaxSum = context.depthMaxSum;
        }

        context.depthMaxSum = root.val;
        // 注意pathMaxSum是全局的, 不能局部直接覆盖了
        int pathMaxSum = root.val;
        if (leftDepthMaxSum > 0) {
            context.depthMaxSum += leftDepthMaxSum;
            pathMaxSum += leftDepthMaxSum;
        }
        if (rightDepthMaxSum > 0) {
            context.depthMaxSum = Math.max(context.depthMaxSum, root.val + rightDepthMaxSum);
            pathMaxSum += rightDepthMaxSum;
        }
        context.pathMaxSum = Math.max(pathMaxSum, context.pathMaxSum);
    }

    public static class Context {
        int depthMaxSum = 0;
        int pathMaxSum = 0;

        public Context(int depthMaxSum, int pathMaxSum) {
            this.depthMaxSum = depthMaxSum;
            this.pathMaxSum = pathMaxSum;
        }
    }

    // 以root为根, 一定经过root的
    public void maxPathSumRecursively2(TreeNode root, Context context) {
        if (root == null) {
            context.depthMaxSum = 0;
            // 这里有问题, root == null时，context.pathMaxSum 被 Integer.MIN_VALUE 覆盖了，不对。
            context.pathMaxSum = Integer.MIN_VALUE;
            return;
        }
        maxPathSumRecursively(root.left, context);
        int leftDepthMaxSum = context.depthMaxSum;

        maxPathSumRecursively(root.right, context);
        int rightDepthMaxSum = context.depthMaxSum;

        // 以下有问题, 有可能不经过left和right
        // context.depthMaxSum = leftDepthMaxSum > rightDepthMaxSum ? leftDepthMaxSum + root.val : rightDepthMaxSum + root.val;
        // context.pathMaxSum = Math.max(root.val + leftDepthMaxSum + rightDepthMaxSum, context.pathMaxSum);

        context.depthMaxSum = root.val;
        // 注意pathMaxSum是全局的, 不能局部直接覆盖了
        int pathMaxSum = root.val;
        if (leftDepthMaxSum > 0) {
            context.depthMaxSum += leftDepthMaxSum;
            pathMaxSum += leftDepthMaxSum;
        }
        if (rightDepthMaxSum > 0) {
            context.depthMaxSum = Math.max(context.depthMaxSum, root.val + rightDepthMaxSum);
            pathMaxSum += rightDepthMaxSum;
        }
        context.pathMaxSum = Math.max(pathMaxSum, context.pathMaxSum);
    }
}
